Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
ТРАНСПОРТНА ЗАДАЧА. МЕТОД ПОТЕНЦІАЛІВ
Лабораторна робота № 4
з дисципліни
" Методи методи дослідження операцій"
Виконав:
ст. гр. КН-4
Львів –2008
Мета роботи: набуття навиків розв’язку транспортної задачі лінійного програмування, вивчення та оволодіння навичками адресації та роботи з формулами в таблицях в Еxcel
Короткі теоретичні відомості
Постановка
В m пунктах виробництва А1, А2, ... ,Аm в наявності запаси якогось однорідного продукту в кількостях а1, а2, ... ,аm одиниць. Необхідність отримання цього продукту в пунктах споживання B1, B2, ... ,Bn складає b1, b2, ... ,bn одиниць відповідно. З кожного пункту виробництва можливе транспортування продукту в будь-який пункт споживання. Транспортні витрати на перевезення одиниці продукції з п. Ai в Bj задані і складають cij, 1 i m, 1 j n.
Розв’язування задачі полягає в тому, щоб знайти такий план перевезень, при якому весь продукт буде вивезено з пунктів виробництва в пункти споживання з мінімальними сумарними транспортними затратами.
Розв’язування
Умови Т-задачі записуються у вигляді
ai
С = EMBED Equation.3 EMBED Equation.3
bj b1 b2 b3 … bn
Введемо змінні хij 0, 1 i m, 1 j n, що означають величину вантажу, який перевозиться з i-ого пункту виробництва в пункт споживання j.
Необхідно знайти множину значень змінних хij 0, мінімізуючи функцію
L = EMBED Equation.3 ,
з виконанням умов
EMBED Equation.3
Матрицю
Х = EMBED Equation.3
називають планом перевезень Т-задачі.
Визначення початкового опорного плану.
Метод «північно-західного кута».
Визначаємо елементи матриці Х0 , починаючи з лівого верхнього кута.
Знаходимо величину х11 = min{a1, b1}. Якщо b1 < a1, то х11 = b1, і перший стовбець «закритий» для розрахунку решти елементів, тобто хі1 = 0, і = 2, ..., m. Якщо b1 > a1, то х11 = a1, і перший рядок «закритий» для розрахунку решти елементів, тобто х1j = 0, j = 2, ..., n.
Припустимо, що вже виконано t кроків.
Тоді обчислення на t + 1 кроці проводиться за наступною схемою. Нехай + = t + 2. Знаходимо x = min{ EMBED Equation.3 }, де
EMBED Equation.3 .
Якщо EMBED Equation.3 , то заповнюється -ий рядок матриці, починаючи з (+1)-го елемента, нулями. Якщо EMBED Equation.3 , то заповнюється нулями -й стовбець, починаючи з (+1)-ї строки. При цьому
EMBED Equation.3
EMBED Equation.3
Приклад.
ai
С = EMBED Equation.3 EMBED Equation.3
bj 70 5 45 70
Перевіряємо умову балансу EMBED Equation.3 ; 190 = 190.
Будуємо початковий опорний план Х0:
Х0 = EMBED Equation.3
x11 = min{60,70} = 60;
x21 = min{55,70-60} = 10;
x22 = min{5, 55-10} = 5;
x23 = min{45,55-10-5} = 40;
x33 = min(40, 45-40} = 5;
x34 = min{70,40-5} = 35;
x44 = 35.
Отриманий початковий опорний план Х0 невироджений.
Метод потенціалів.
Алгоритм методу потенціалів розв’язування Т-задачі складається з попереднього етапу і скінченного числа ітерацій.
Попередній етап.
Будується початковий опорний план Х0.
Обчислюється оціночна матриця
С1 = EMBED Equation.3 ,
де vj i ui – потенціали i-ого пункту виробництва та пункту споживання j, для яких виконується умова EMBED Equation.3 і хij 0. Для зручності вибирається u1 = 0. Позиція в матриці С1, яка відповідає...
